﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using Xunit;
namespace LeetCode.CodeDay
{
    public partial class Code
    {
        /// <summary>
        /// .*正则匹配
        /// </summary>
        /// <param name="s"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        public bool IsMatch(string s, string p)
        {
            if (s == null || p == null)
                return false;

            int ls = s.Length;
            int lp = p.Length;
            if (ls == lp && ls == 0)
                return true;
            bool[,] f = new bool[ls + 1, lp + 1];
            f[0, 0] = true;
            Func<string, string, int, int, bool> isMatch = (string str1, string str2, int n1, int n2) =>
            {
                if (n1 == 0)
                    return false;
                if (str1[n1 - 1] == str2[n2 - 1])
                    return true;
                if (str2[n2 - 1] == '.')
                    return true;
                return false;
            };

            for (int i = 0; i <= ls; i++)
            {
                for (int j = 1; j <= lp; j++)
                {
                    if (p[j - 1] == '*')
                    {
                        if (isMatch(s, p, i, j - 1))
                            f[i, j] = f[i, j - 2] || f[i - 1, j];
                        else
                        {
                            f[i, j] = f[i, j - 2];
                        }
                    }
                    else
                    {
                        if (isMatch(s, p, i, j))
                        {
                            f[i, j] = f[i - 1, j - 1];
                        }
                        else
                            f[i, j] = false;
                    }

                }
            }


            return f[ls, lp];
        }
        /// <summary>
        /// 罗马数转整数
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int RomanToInt(string s)
        {
            if (string.IsNullOrWhiteSpace(s))
                return 0;
            Dictionary<char, int> dict = new Dictionary<char, int> {
                { 'I',1},
                { 'V',5},
                { 'X',10},
                { 'L',50},
                { 'C',100},
                { 'D',500},
                { 'M',1000}
            };
            Dictionary<char, List<char>> descMap = new Dictionary<char, List<char>>() {
                { 'I',new List<char>{ 'V','X'} },
                { 'X',new List<char>{ 'L','C'} },
                { 'C',new List<char>{ 'D','M'} }
            };
            int num = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (descMap.Keys.Contains(s[i]) && (i + 1) < s.Length && descMap[s[i]].Contains(s[i + 1]))
                {
                    num += dict[s[i]] * (-1) + dict[s[i + 1]];
                    i++;
                }
                else
                {
                    num += dict[s[i]];
                }
            }
            return num;
        }
        /// <summary>
        /// 最长前缀
        /// </summary>
        /// <param name="strs"></param>
        /// <returns></returns>
        public string LongestCommonPrefix(string[] strs)
        {
            var first = strs[0];
            if (strs.Count() == 1)
                return first;
            bool breaks = false;
            string result = "";
            for (int i = 0; i < first.Length && breaks == false; i++)
            {
                char c = first[i];
                for (int j = 1; j < strs.Count() && breaks == false; j++)
                {
                    if (strs[j].Length < (i + 1) || strs[j][i] != c)
                        breaks = true;
                }
                if (breaks == false)
                    result += c;
            }
            return result;
        }
        /// <summary>
        /// 三数之和
        /// </summary>
        /// <param name="nums">
        /// 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
        /// 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
        /// 你返回所有和为 0 且不重复的三元组。
        /// 注意：答案中不可以包含重复的三元组
        /// <returns></returns>
        public IList<IList<int>> ThreeSum(int[] numss)
        {
            var nums = numss.OrderBy(s => s).ToList();

            List<IList<int>> dict = new List<IList<int>>();
            for (int i = 0; i < nums.Count - 2; i++)
            {
                if (nums[i] > 0)
                    break;
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                int left = i + 1;
                int right = nums.Count - 1;
                while (left < right)
                {
                    int total = nums[i] + nums[left] + nums[right];
                    if (total > 0)
                        right--;
                    if (total < 0)
                        left++;
                    if (total == 0)
                    {
                        dict.Add(new List<int>() { nums[i], nums[left], nums[right] });
                        while (left < right && nums[left] == nums[left + 1])
                            left++;
                        while (left < right && nums[right] == nums[right - 1])
                            right--;
                        left++;
                        right--;
                    }
                }

            }
            return dict;
        }
        /// <summary>
        /// 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
        /// 返回这三个数的和。
        /// 假定每组输入只存在恰好一个解 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int ThreeSumClosest(int[] nums, int target)
        {
            var list = nums.OrderBy(s => s).ToList();
            var count = list.Count;
            int minSum = list[0] + list[1] + list[2];

            Func<int, int, int> getMinSum = (oldSum, newSum) =>
            {
                var a1 = newSum - target;
                var newMinSum = a1 < 0 ? a1 * (-1) : a1;
                var b1 = oldSum - target;
                var oldMinSum = b1 < 0 ? b1 * (-1) : b1;
                if (newMinSum < oldMinSum)
                    return newSum;
                return oldSum;
            };

            for (int i = 0; i < count - 2; i++)
            {
                int left = i + 1;
                int right = count - 1;
                if (i > 0 && list[i] == list[i - 1]) continue;
                while (left < right)
                {
                    var sum = list[i] + list[left] + list[right];
                    minSum = getMinSum(minSum, sum);
                    int rase = sum - target;
                    if (rase < 0)
                    {
                        left++;
                        while (left < right && list[left] == list[left - 1])
                            left++;

                    }
                    else if (rase > 0)
                    {
                        right--;
                        while (left < right && list[right] == list[right + 1])
                            right--;
                    }
                    else
                        return sum;
                }
            }
            return minSum;
        }
        /// <summary>
        /// 电话号码的字母组合
        /// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
        /// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
        /// </summary>
        /// <param name="digits"></param>
        /// <returns></returns>
        public IList<string> LetterCombinations(string digits)
        {
            Dictionary<char, List<char>> charMap = new Dictionary<char, List<char>> {
                { '2',new List<char>{'a','b','c' } },
                { '3',new List<char>{'d','e','f' }},
                { '4',new List<char>{'g','h','i' }},
                { '5',new List<char>{'j','k','l' }},
                { '6',new List<char>{'m','n','o' }},
                { '7',new List<char>{'p','q','r','s' }},
                { '8',new List<char>{'t','u','v' }},
                { '9',new List<char>{'w','x','y','z' }},
            };


            var result = new List<string>();
            if (digits.Length == 0)
            {
                return result;
            }
            List<List<char>> data = new List<List<char>>();
            Func<List<string>, List<char>, List<string>> getStringList = (t1, c1) =>
            {
                var rs = new List<string>();
                foreach (var cv in c1)
                {
                    if (t1.Any())
                    {
                        foreach (var t in t1)
                        {
                            rs.Add(t + cv);
                        }
                    }
                    else
                    {
                        rs.Add(cv.ToString());
                    }
                }
                return rs;
            };

            for (int i = 0; i < digits.Length; i++)
            {
                result = getStringList(result, charMap[digits[i]]);
            }
            return result;
        }
        /// <summary>
        /// 四数之和
        /// </summary>
        /// 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
        /// 请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 
        /// （若两个四元组元素一一对应，则认为两个四元组重复)
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public IList<IList<int>> FourSum(int[] nums, int target)
        {
            List<IList<int>> result = new List<IList<int>>();
            var list = nums.OrderBy(_ => _).ToList();
            for (int i = 0; i < list.Count - 3; i++)
            {
                if (i > 0 && list[i] == list[i - 1]) continue;
                long a1 = 0L + list[i] + list[i + 1] + list[i + 2] + list[i + 3];
                if (a1 > target)
                    break;
                var lastIndex = list.Count - 1;
                long a2 =0L+ list[i] + list[lastIndex - 2] + list[lastIndex - 1] + list[lastIndex];
                if ( a2 < target)
                    continue;
                for (int j = i + 1; j < list.Count - 2; j++)
                {
                    int left = j + 1;
                    int right = list.Count - 1;
                    long s1 = 0L + list[i] + list[j] + list[left] + list[left + 1];
                    if (s1 > target)
                        break;
                    long s2 = 0L + list[i] + list[j] + list[right - 1] + list[right];
                    if (s2 < target)
                        continue;
                    if (j > i+1 && list[j] == list[j - 1]) continue;
                    while (left < right)
                    {
                        long s = 0L + list[i] + list[j] + list[left] + list[right];
                        if (s > target)
                        {
                            right--;
                        }
                        if (s < target)
                            left++;
                        if (s == target)
                        {
                            result.Add(new List<int> { list[i], list[j], list[left], list[right] });
                            while (left < right && list[left] == list[left + 1])
                                left++;
                            while (left < right && list[right] == list[right - 1])
                                right--;
                            left++;
                            right--;
                        }
                    }


                }
            }
            return result;
        }

    }
}